// 简易版线性探查法哈希表实现
public class ExampleLinearProbingHashMap1 {

    private static class Node {
        int key;
        int value;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 哈希表的底层数组，每个索引存储一个键值对
    private final Node[] table;

    public ExampleLinearProbingHashMap1(int capacity) {
        table = new Node[capacity];
    }

    // 增、改
    public void put(int key, int value) {
        int index = findKeyIndex(key);
        table[index] = new Node(key, value);
    }

    // 查，找不到就返回-1
    public int get(int key) {
        int index = findKeyIndex(key);
        return table[index] == null ? -1 : table[index].value;
    }

    // 删
    public void remove(int key) {
        int index = findKeyIndex(key);
        if (table[index] == null)
            return;
        table[index] = null;
        // 保持元素连续性，搬移数据（该过程称为rehash）
        index = (index + 1) % table.length;
        while (table[index] != null) {
            Node entry = table[index];
            table[index] = null;
            // 这个方法很关键，利用put方法，将键值对重新插入
            // 这样就能把它们移动到正确的table索引位置
            put(entry.key, entry.value);
            index = (index + 1) % table.length;
        }
    }
    // 线性探测法查找key在table中的索引
    // 如果找不到，返回的就是下一个为null的索引，可用于插入
    private int findKeyIndex(int key) {
        int index = hash(key);
        while (table[index] != null) {
            if (table[index].key == key) {
                return index;
            }
            // 注意环形数组特性
            index = (index + 1) % table.length;
        }

        return index;
    }

    private int hash(int key) {
        return key % table.length;
    }
}
